/*
day322 
2020.7.15 
*/
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
using namespace std;

 
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
		unordered_map<int,vector<int>> m;
		int i_size=mat.size();
		int j_size=mat.front().size();
		
		for(int i=0;i<i_size;++i)
		{
			for(int j=0;j<j_size;++j)
			{
				m[i-j].push_back(mat[i][j]);
			}
		}
		
		for(auto &v : m)
		{
			sort(v.second.begin(),v.second.end());
		}
		
		for(int i=i_size-1;i>=0;--i)
		{
			for(int j=j_size;j>=0;--j)
			{
				mat[i][j]=m[i-j].back();
				m[i-j].pop_back();
			}
		}
		
		return mat;
    }
};

int main()
{
	
	return 0;
}
